package com.sk.leetcode.arithmetic.test11_20;

/**
 * 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
 * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 * <p>
 * 示例:
 * 输入: [1,8,6,2,5,4,8,3,7]
 * 输出: 49
 */
public class Test11 {

    public static void main(String[] args) {
        int[] height = {2, 2};
        int ret = maxArea(height);
        System.out.println(ret);
    }

    public static int maxArea(int[] height) {
        int[][] heightLeft = new int[height.length][2];
        int[][] heightRight = new int[height.length][2];
        heightLeft[0][0] = height[0];
        heightLeft[0][1] = 0;

        heightRight[0][0] = height[height.length - 1];
        heightRight[0][1] = height.length - 1;

        int indexl = 0, indexr = 0, he = height.length;
        for (int i = 1; i < he; i++) {
            int l = height[i], ll = heightLeft[indexl][0];
            int r = height[he - i - 1], rr = heightRight[indexr][0];
            if(l > ll) {
                heightLeft[++indexl][0] = height[i];
                heightLeft[indexl][1] = i;
            }
            if(r > rr) {
                heightRight[++indexr][0] = height[he - 1 - i];
                heightRight[indexr][1] = he - 1 - i;
            }
        }
        int pro = 0;
        for (int i = indexl; i >= 0; i--) {
            for (int j = indexr; j >= 0; j--) {
                int hl = heightLeft[i][0];
                int hr = heightRight[j][0];

                int c = heightRight[j][1] - heightLeft[i][1];
                int ret = hl * c;
                if(hl > hr) {
                    ret = hr * c;
                }
                if(ret > pro) {
                    pro = ret;
                }
            }
        }
        return pro;
    }
}
